1. Field of the Invention
The present invent ion relates to a modulo reduction method using a precomputed table to increase a reduction speed by reducing the number of addition operations during the execution of ordinary operational processes using computers.
2. Description of the Prior Art
The recent increasing need for information protection has brought to us the need of implementation of a mechanism for information protection, whose characteristics requires modulo arithmetic of very large numbers. Particularly, the need of high speed modulo reduction algorithms has increased in proportion to the increasing need of involution operations.
Most information protection mechanisms need to be implemented on smart cards under various limited operational conditions, in terms of the size of the memory and the speed of processors, or the like, used on the smart cards.
For this reason, we can consider operational techniques, which use a precomputed table stored in an appropriate size of a memory, to convert all of the muliplications needed for reduction operations into additions. Conventional reduction techniques have drawbacks in that they require many operations and are not efficient.
Modulo arithmetic refers to an operation that obtains a remainder from the division of a number X, which is greater than N by N, for a given modulo N. Modulo arithmetic used in an information protection mechanism, where N is an ordinary number having more than 512 bits, which can not be handled at one time, requires a multi-precision operation.
The most essential part of a modulo operation method or algorithm is the part which performs the modulo arithmetic. There are, in general, two methods for performing a modulo reduction. One is a method that uses real division in performing a reduction, the other is the method that uses addition only, i.e., not division. The method that uses division does not need to use a precomputed table, while the method which does not use division needs a precomputed table.
Conventional modulo reduction algorithms using precomputed tables can be explained with references to FIG. 1, FIG. 2, and FIG. 3. as follows:
FIG. 1 shows a table configuration used in conventional modulo reduction algorithms; FIG. 2 illustrates a structure for inputting data into a modulo reduction algorithm; and FIG. 3 shows a flow of a modulo reduction algorithm using a table.
In this application, X represents an input (2.sup.n .ltoreq.X&lt;2.sup.n +log.sub.2 t), X.sub.-- R an upper log.sub.2 t bit number of X, X.sub.-- R a lower n bit number of X and N also modulo, respectively.
The reference number 1, in FIG. 1, represents the ith content (1.ltoreq.i.ltoreq.t-1) stored in the table, the number 2, in FIG. 2, represents an upper (r-n) bit of the reference number, which consists of maximum r bits (n&lt;r.ltoreq.n +log.sub.2 t), and is to be reduced, and the number 3 represents a lower n bits, which need not be reduced respectively, while the number 4, in FIG. 3, represents a modulo reduction process of a conventional algorithm, and the number 5 represents the checking of an overflow.
Letting N be an n bit number, an algorithm using the conventional table will operate as shown in FIG. 3. First, assume a number, which is constructed as shown in FIG. 2, is to be inputted. Let the inputted number be X where X can be divided such that X=X.sub.-- 0.multidot.2.sup.2 +X.sub.-- R, and with reference to the n bit, such that X(mod N)=(X.sub.-- 0.multidot.2 .sup.n (mod N)+X.sub.-- R)(mod N). Here, the results stored previously in the table , as shown in FIG. 1, can be searched for with an index of X.sub.-- 0.multidot.2.sup.n (mod N). The X.sub.-- 0.multidot.2.sup.n (mod N) found in this way can be added to X.sub.-- R to make a new X'. In this case, an overflow bit can occur in the (n+1)th bit, since X.sub.-- 0.multidot.2.sup.n (mod N) and X.sub.-- R are maximum n bit numbers respectively. If an overflow occurs, the above process will be repeated with the X' being inputted. If not, the reduction process will be finished. However, a subtraction may be needed after comparing the final result with N, since the final result can be greater than N, even though it has n bits.
As explained above, the Prior Art requires repetition of the reduction process, which refers to the table, when overflows occur. Since the maximum number of times an execution of the reduction process is not fixed, there exists a problem in that the reduction operation has to be executed many times.